package uestc.lj.midPromotion.dfs;

import uestc.lj.leetcode.day1.LeetCode;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.regex.Matcher;

/**
 * 数组arr代表每一个咖啡机冲一杯咖啡的时间，每个咖啡机只能串行的制造咖啡，有n个人需要喝咖啡
 * 每个人喝完之后咖啡杯可以选择清洗或者自然挥发干净，只有一台洗咖啡杯的机器，只能串行的洗咖啡杯
 * 洗杯子的机器洗完一个杯子的时间为a，任何一个杯子自然挥发干净的时间为b
 * 假设时间从0开始，返回所有人喝完咖啡并洗完咖啡杯的全部过程结束后，至少来到什么时间点
 *
 * @Author:Crazlee
 * @Date:2021/12/1
 */
public class Code06_Coffee {
	/**
	 * 暴力尝试方法
	 *
	 * @param arr 冲咖啡的时间
	 * @param n   n个人
	 * @param a   洗杯子的时间
	 * @param b   杯子自然挥发的时间
	 * @return 最少的时间点
	 */
	public static int minTime1(int[] arr, int n, int a, int b) {
		int[] times = new int[arr.length];
		int[] drink = new int[n];
		return forceMake(arr, times, 0, drink, n, a, b);
	}

	private static int forceMake(int[] arr, int[] times, int kth, int[] drink, int n, int a, int b) {
		if (kth == n) {
			int[] drinkSorted = Arrays.copyOf(drink, kth);
			Arrays.sort(drinkSorted);
			return forceWash(drinkSorted, a, b, 0, 0, 0);
		}
		int time = Integer.MAX_VALUE;
		for (int i = 0; i < arr.length; i++) {
			int work = arr[i];
			int pre = times[i];
			drink[kth] = pre + work;
			times[i] = pre + work;
			time = Math.min(time, forceMake(arr, times, kth + 1, drink, n, a, b));
			drink[kth] = 0;
			times[i] = pre;
		}
		return time;
	}

	private static int forceWash(int[] drinks, int a, int b, int index, int washLine, int time) {
		if (index == drinks.length) {
			return time;
		}
		int wash = Math.max(drinks[index], washLine) + a;
		int ans1 = forceWash(drinks, a, b, index + 1, wash, Math.max(wash, time));

		int dirty = drinks[index] + b;
		int ans2 = forceWash(drinks, a, b, index + 1, washLine, Math.max(dirty, time));

		return Math.min(ans1, ans2);
	}

	//====================================================================================================

	public static class Machine {
		public int timePoint;
		public int workTime;

		public Machine(int timePoint, int workTime) {
			this.timePoint = timePoint;
			this.workTime = workTime;
		}
	}

	public static class MachineComparator implements Comparator<Machine> {

		@Override
		public int compare(Machine o1, Machine o2) {
			return (o1.timePoint + o1.workTime) - (o2.timePoint + o2.workTime);
		}
	}

	public static int minTime2(int[] arr, int n, int a, int b) {
		PriorityQueue<Machine> heap = new PriorityQueue<>(new MachineComparator());
		for (int i = 0; i < arr.length; i++) {
			heap.add(new Machine(0, arr[i]));
		}
		int[] drinks = new int[n];
		for (int i = 0; i < n; i++) {
			Machine cur = heap.poll();
			cur.timePoint += cur.workTime;
			drinks[i] = cur.timePoint;
			heap.add(cur);
		}
		return process(drinks, a, b, 0, 0);
	}

	/**
	 * @param drinks   所有人喝完的时间
	 * @param a        洗杯子的时间
	 * @param b        杯子自然挥发的时间
	 * @param index    当前第几个人
	 * @param washLine 洗咖啡的机器什么时候有空
	 * @return 洗完drinks[index...N-1]最少的时间点
	 */
	private static int process(int[] drinks, int a, int b, int index, int washLine) {
		if (index == drinks.length - 1) {
			return Math.min(Math.max(washLine, drinks[index]) + a, drinks[index] + b);
		}
		// 当前咖啡杯放到咖啡机中去洗
		int wash = Math.max(washLine, drinks[index]) + a;
		// 洗完剩下所有咖啡杯的最早时间
		int next1 = process(drinks, a, b, index + 1, wash);

		int p1 = Math.max(wash, next1);

		// 当前咖啡杯选择自然挥发
		int dirty = drinks[index] + b;
		// 洗完剩下所有咖啡杯的最早时间
		int next2 = process(drinks, a, b, index + 1, washLine);

		int p2 = Math.max(dirty, next2);

		return Math.min(p1, p2);
	}
	//================================================================================================

	public static int minTime3(int[] arr, int n, int a, int b) {
		PriorityQueue<Machine> heap = new PriorityQueue<>(new MachineComparator());
		for (int i = 0; i < arr.length; i++) {
			heap.add(new Machine(0, arr[i]));
		}
		int[] drinks = new int[n];
		for (int i = 0; i < n; i++) {
			Machine cur = heap.poll();
			cur.timePoint += cur.workTime;
			drinks[i] = cur.timePoint;
			heap.add(cur);
		}
		if (a >= b) {
			return drinks[n - 1] + b;
		}
		int[][] dp = new int[n][drinks[n - 1] + n * a];

		for (int i = 0; i < dp[0].length; i++) {
			dp[n - 1][i] = Math.min(Math.max(i, drinks[n - 1]) + a, drinks[n - 1] + b);
		}

		for (int row = n - 2; row >= 0; row--) {
			int washLine = drinks[row] + (row + 1) * a;
			for (int col = 0; col < washLine; col++) {
				int wash = Math.max(col, drinks[row]) + a;
				dp[row][col] = Math.min(Math.max(wash, dp[row + 1][wash]),
						Math.max(drinks[row] + b, dp[row + 1][Math.max(col, drinks[row] + b)]));
			}
		}
		return dp[0][0];
	}

}
